package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/04 11:10
 **/
public class Day2_3_Num6168_NumberOfWays {
    public static void main(String[] args) {
        System.out.println(numberOfWays(89,100, 99));
    }
    public static int numberOfWays(int startPos, int endPos, int k) {
        return (int)dfs(startPos, endPos, k, 0);
    }
    private static long dfs(int startPos, int endPos, int k, int step){
        if((Math.abs(endPos-startPos) > (k-step))) return 0;
        if(step >= k){
            if(startPos == endPos) return 1;
            else return 0;
        }
        return (dfs(startPos+1, endPos, k, step+1)+dfs(startPos-1, endPos, k , step+1)) % 1000000007;
    }

}